package com.leetcode.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:给你一个由'1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 *
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 *
 * 此外，你可以假设该网格的四条边均被水包围。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-islands
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-03-16
 * Time:22:17
 */
public class DFS200 {
    public int[][] d = {{1,0},{-1,0},{0,1},{0,-1}};
    public int numIslands(char[][] grid) {
        if(grid == null)return 0;
        int row = grid.length;
        int col = grid[0].length;
        boolean[][] bool = new boolean[row][col];//标记位

        int num = 0;
        for(int i = 0;i < row;i ++){
            for(int j = 0;j < col;j ++){
                if(grid[i][j] == '1' && !bool[i][j]){
                    num ++;
                    DFS(grid,row,col,bool,i,j);//有效的搜索,搜索过后连接此块陆地的标记为都会置为true就不会再进行搜索了直至下一块土地的出现 又会进行同样的搜索
                }
            }
        }
        return num;
    }
    public void DFS(char[][] grid,int row,int col,boolean[][] bool,int curX,int curY){
        //当前该干什么
        bool[curX][curY] = true;
        //接下来干什么
        for(int i = 0;i < 4;i ++){//看其四个方向的位置是不是满足陆地的条件,是否应该置为true
            int newX = curX + d[i][0];
            int newY = curY + d[i][1];
            if(newX >= row || newX < 0
                    || newY >= col || newY < 0){
                continue;
            }
            if(grid[newX][newY] == '1' && !bool[newX][newY]){
                DFS(grid,row,col,bool,newX,newY);
            }
        }
    }
}
